package com.sheng.leetcode.year2022.month07.day13;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/07/13
 *
 * 735. 行星碰撞
 *
 * 给定一个整数数组 asteroids，表示在同一行的行星。
 * 对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
 * 找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。
 * 两颗移动方向相同的行星，永远不会发生碰撞。
 *
 * 示例 1：
 * 输入：asteroids = [5,10,-5]
 * 输出：[5,10]
 * 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
 *
 * 示例 2：
 * 输入：asteroids = [8,-8]
 * 输出：[]
 * 解释：8 和 -8 碰撞后，两者都发生爆炸。
 *
 * 示例 3：
 * 输入：asteroids = [10,2,-5]
 * 输出：[10]
 * 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
 *
 * 提示：
 *
 * 2 <= asteroids.length <= 104
 * -1000 <= asteroids[i] <= 1000
 * asteroids[i] != 0
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/asteroid-collision
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0735 {

    @Test
    public void test01() {
//        int[] asteroids = {5,10,-5};
//        int[] asteroids = {8,-8};
//        int[] asteroids = {10,2,-5};
//        int[] asteroids = {-11,5,10,-5};
//        int[] asteroids = {-11,5,10,-5,-12};
        int[] asteroids = {1,-1,-2,-2};
        int[] ints = new Solution().asteroidCollision(asteroids);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }

}
class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        // 数组总长度
        int length = asteroids.length;
        // 返回数组，将碰撞后剩余的留下放入数组
        int[] ints = new int[length];
        // 存放到ints中的元素个数
        int index = 0;
        // 数组开头的负数忘左方向前行，永不碰撞，所以第一个产生碰撞的是从正数开始，直到第一个负数出现开始发生碰撞
        for (int i = 0; i < length; i++) {
            if (asteroids[i] < 0) {
                if (index == 0) {
                    // 第一个数是负数
                    ints[index++] = asteroids[i];
                } else if (ints[index - 1] < 0) {
                    // 当前数为负数，前一个数也是负数
                    ints[index++] = asteroids[i];
                } else {
                    // 当前数是负数，前一个数是正数,发生碰撞的情况
                    if (Math.abs(asteroids[i]) == ints[index - 1]) {
                        // 相等，全部撞毁
                        index--;
                    } else if (Math.abs(asteroids[i]) > ints[index - 1]) {
                        // 负数比前一个正数要大
                        while (index > 0 && ints[index - 1] > 0 && Math.abs(asteroids[i]) > ints[index - 1]) {
                            index--;
                        }
                        // 跳出while循环的三种可能
                        // 1、前面全是正数，而且都比当前负数值小，全部撞毁，当前负数到达index = 0的位置
                        // 2、当前数前面的正数全都不如当前值，全部撞毁，然后遇见的负数
                        // 3、当前数撞毁一部分正数后，遇见值比它大或者相等的正数（补充：被撞毁或同归于尽）
                        if (index == 0 || ints[index - 1] < 0) {
                            // 第1,2种可能性
                            ints[index++] = asteroids[i];
                        } else if (ints[index - 1] == Math.abs(asteroids[i])) {
                            index--;
                        }
                    }
                }
            } else {
                // 不管当前正数值的前一个值是正数还是负数，都可以直接插入
                ints[index++] = asteroids[i];
            }
        }
        // 返回数组中对应数量的值
        return Arrays.copyOf(ints, index);
    }
}
